1353E - K-periodic Garland - CodeForces Solution

brute force dp greedy *1900

Please click on ads to support us..

Python Code: 

for _ in range(int(input())):
    n, k = map(int, input().split())
    s = input()
    ans = []
    for i in range(k):
        c = t = 0
        for j in range(i, n, k):
            if s[j] == '1':
                c += 1
            else:
                c -= 1
            t = min(t, c)
            ans += c - t,
    print(s.count('1') - max(ans))

C++ Code: 

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, k;

        cin >> n >> k;

        string s;

        cin >> s;

        // int pre[n];
        vector<int> pre(n, 0);
        for (int i = 0; i < n; i++)
        {
            if (i == 0)
                pre[i] = s[i] - '0';
            else
                pre[i] += pre[i - 1] + (s[i] - '0');
        }

        vector<int> sum(n, 0);
        for (int i = n - 1; i >= 0; i--)
        {
            int xr = (s[i] - '0') ^ 1;
            if (i + k - 1 < n)
            {
                xr += pre[i + k - 1] - pre[i];
            }
            else
            {
                xr += pre[n - 1] - pre[i];
            }
            if (i + k < n)
            {
                xr += sum[i + k];
            }
            int r = pre[n - 1] - pre[i] + (s[i] - '0');
            sum[i] = min(r, xr);
        }
        int cnt = 1e15;
        for (int i = 0; i < n; i++)
        {
            int s = sum[i];
            if (i)
                s += pre[i - 1];

            cnt = min(cnt, s);
        }
        cout << cnt << endl;
    }
    // int i = 0, j = n - 1;
    // while (i < n && s[i] == '0')
    //     i++;
    // while (j >= 0 && s[j] == '0')
    //     j--;
    // if (j < i)
    // {
    //     cout << "0" << endl;
    //     continue;
    // }
    // int total = 0;
    // for (int l = i; l <= j; l++)
    // {
    //     if (s[l] == '1')
    //     {
    //         total++;
    //     }
    // }
    // vector<int> rem(k + 1, 0);
    // for (int l = i; l <= j; l++)
    // {
    //     if (s[l] == '1')
    //     {
    //         rem[(l - i) % (k)]++;
    //     }
    // }
    // int ans = 1e6;
    // cout << total << endl;
    // cout << (j - i + 1) / k << endl;

    // for (int l = 0; l < k; l++)
    // {
    //     cout << rem[l] << " ";
    //     ans = min(ans, (j - i + 1) / k - rem[l] + total - rem[l]);
    //     cout << ans << " ";
    // }
    // cout << ans << endl;
}


Comments

Submit
0 Comments
More Questions

3B - Lorry
1392A - Omkar and Password
489A - SwapSort
932A - Palindromic Supersequence
433A - Kitahara Haruki's Gift
672A - Summer Camp
1277A - Happy Birthday Polycarp
577A - Multiplication Table
817C - Really Big Numbers
1355A - Sequence with Digits
977B - Two-gram
993A - Two Squares
1659D - Reverse Sort Sum
1659A - Red Versus Blue
1659B - Bit Flipping
1480B - The Great Hero
1519B - The Cake Is a Lie
1659C - Line Empire
515A - Drazil and Date
1084B - Kvass and the Fair Nut
1101A - Minimum Integer
985D - Sand Fortress
1279A - New Year Garland
1279B - Verse For Santa
202A - LLPS
978A - Remove Duplicates
1304A - Two Rabbits
225A - Dice Tower
1660D - Maximum Product Strikes Back
1513A - Array and Peaks